package q856_scoreOfParentheses;

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution_2 {
    /*
    栈可以帮助将时间复杂和空间复杂降到n
    遇到左括号，那么我们需要计算该左括号内部的子平衡括号字符串 A 的分数，
    我们也要先压入分数 0，表示 A 前面的空字符串的分数。
    遇到右括号，说明该右括号内部的子平衡括号字符串 A 的分数已经计算出来了，
    我们将它弹出栈，并保存到变量 v 中。如果 v = 0，那么说明子平衡括号字符串 A 是空串，
    (A) 的分数为 1，否则 (A) 的分数为 2v，然后将 (A) 的分数加到栈顶元素上。
     */
    public int scoreOfParentheses(String s) {
        Deque<Integer> st = new ArrayDeque<Integer>();
        st.push(0);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                st.push(0);
            } else {
                int v = st.pop();
                int top = st.pop() + Math.max(2 * v, 1);
                st.push(top);
            }
        }
        return st.peek();
    }
}
